from typing import Optional
import graphviz

g = graphviz.Graph()
g.node
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __str__(self):
        return '%d' % self.val


class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        inf = 10 ** 10
        result = [-inf]
        def dfs(u: TreeNode):
            c = d = e = f = -inf
            if u.left:
                c, d = dfs(u.left)
            if u.right:
                e, f = dfs(u.right)
            a = max([c, d, e, f])
            b = max(u.val, max(d, f) + u.val)
            result[0] = max([result[0], a, b, d + f + u.val])
            return a, b

        dfs(root)
        return result[0]


null = None
def lst2tree(lst):
    nodes = [TreeNode(x) if x is not None else None for x in lst]
    for i in range(len(nodes)):
        if nodes[i] is not None:
            if 2 * i + 1 < len(nodes):
                nodes[i].left = nodes[2 * i + 1]
            if 2 * i + 2 < len(nodes):
                nodes[i].right = nodes[2 * i + 2]
    root = nodes[0]
    return root


# res1 = Solution().maxPathSum(lst2tree([1, 2, 3]))
# print(res1)

# res1 = Solution().maxPathSum(lst2tree([-10,9,20,null,null,15,7]))
# print(res1)
